• Home
• Staff & Students
• Vacancies

 

Csaba Szepesvári

 

Tuesday 10th November 2015

Time: 4.00pm

 

Ground Floor Seminar Room

25 Howland Street, London, W1T 4JG

 

(Bandit) Convex Optimization with Biased Noisy Gradient Oracles

 

For bandit convex optimization we propose a model, where a gradient
estimation oracle acts as an intermediary between
a noisy function evaluation oracle and the algorithms. The algorithms
can control the bias-variance tradeoff in the gradient estimates. We
prove lower and upper bounds for the minimax error of algorithms that
interact with the objective function by controlling this oracle. The
upper bounds replicate many existing results (capturing the essence of
existing proofs) while the lower bounds put a limit on the achievable
performance in this setup. In particular, our results imply that no
algorithm can achieve the optimal minimax error rate in stochastic
bandit smooth convex optimization.